package leecode

func maxSlidingWindow(nums []int, k int) []int {
	dqueue := NewMyQueue()
	result := make([]int, 0)
	//先将前k个元素放入队列
	for i := 0; i < k; i++ {
		dqueue.push(nums[i])
	}
	//拿到最大值
	result = append(result, dqueue.front())
	for i := k; i < len(nums); i++ {
		//移除最前面的元素
		dqueue.pop(nums[i-k])
		//向队列后面追加元素
		dqueue.push(nums[i])
		//得到最大值
		result = append(result, dqueue.front())
	}
	return result
}

type MyQueue239 struct {
	queue []int
}

func NewMyQueue() *MyQueue239 {
	return &MyQueue239{queue: make([]int, 0)}
}

// 得到窗口最大值
func (m *MyQueue239) front() int {
	return m.queue[0]
}

func (m *MyQueue239) pop(val int) {
	//因为队列此时只存放每一次窗口的最大值,所以当value为当前窗口最大值时,才移除
	//移除队列的元素是窗口最大值
	if len(m.queue) > 0 && val == m.front() {
		m.queue = m.queue[1:]
	}
}

func (m *MyQueue239) push(value int) {
	//如果加入的值比队列末尾的值大,移除队列末尾的元素,使队列为单调递减
	for len(m.queue) > 0 && value > m.queue[len(m.queue)-1] {
		m.queue = m.queue[:len(m.queue)-1]
	}
	m.queue = append(m.queue, value)
}
